package com.tgy.programmer_code_interview_guide._03_binarytree;

import com.tgy.leetcode.TreeNode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @Author: tgy
 * @Date: 2/5/21 11:25 AM
 */
public class _07_找到二叉树中符合搜索二叉树条件的最大拓扑结构 {

    /**
     * 从每一个节点开始作为搜索二叉树向下查找节点，
     * @param root
     * @return
     */
    public static int findMaxSearchTree(TreeNode root) {

        if (root == null) {

            return 0;
        }

        int count = findMaxSearchTreeByTreeNode(root,root);
        int leftCount = findMaxSearchTree(root.left);
        int rightCount = findMaxSearchTree(root.right);

        System.out.println(count + ":" + leftCount + ":" + rightCount);

        return Math.max(rightCount,Math.max(count,leftCount));
    }


    private static int findMaxSearchTreeByTreeNode(TreeNode node, TreeNode addNode) {

        if (addNode == null) {

            return 0;
        }

        return findNode(node,addNode) ? findMaxSearchTreeByTreeNode(node,addNode.left) + findMaxSearchTreeByTreeNode(node,addNode.right) + 1:0;
    }

    private static boolean findNode(TreeNode node, TreeNode fNode) {


        if (node == null) {

            return false;
        }

        if (node.val == fNode.val) {

            return true;
        }

        return findNode(node.val < fNode.val ? node.right:node.left,fNode);
    }

    private static int findMax(TreeNode node,int min,int max) {

        if (node == null) {

            return 0;
        }

        if (node.val <= min || node.val >= max) {

            return 0;
        }

        int leftNum = findMax(node.left,min,node.val);
        int rightNum = findMax(node.right,node.val,max);
        return 1 + leftNum + rightNum;
    }

    public static void main(String[] args) {

        TreeNode root = new TreeNode(6);

        root.left = new TreeNode(1);
        root.left.left = new TreeNode(0);
        root.left.right = new TreeNode(3);

        root.right = new TreeNode(12);
        root.right.left = new TreeNode(10);
        root.right.left.left = new TreeNode(4);
        root.right.left.left.left = new TreeNode(2);
        root.right.left.left.right = new TreeNode(5);
        root.right.left.right = new TreeNode(14);
        root.right.left.right.left = new TreeNode(11);
        root.right.left.right.right = new TreeNode(15);

//        root.right.right = new TreeNode(13);
//        root.right.right.left = new TreeNode(20);
//        root.right.right.right = new TreeNode(16);

        int num = findMaxSearchTree(root);

        System.out.println(num);
    }

}
